Cryptography is a generally used term covering science and technology concerned with transforming data, so as to be able to store and transmit the data while being able to prevent unauthorized access to the data. By means of cryptography, the data are made non-comprehensible for any other person but the intended recipient or recipients of the data. Accordingly, cryptography plays an increasingly more important role in the protection of intellectual property, including copyright protection, as the technological advancements require safe transmission and storage of huge amounts of data.
In an encryption and decryption algorithm, the specific transformation of data is dependent on an input to the algorithm, a so-called key. In case the sender and the recipient of the data have an appropriate set of keys, the sender and the recipient are able to correctly encrypt and decrypt the data while any third person who may gain access to the encrypted data is not able to view a properly decrypted version of the encrypted data, as she or he is not in possession of an appropriate key.
Usually, a set of data to be encrypted is referred to as “plaintext” or “original data”, whereas the encrypted version of the set of data is referred to as “ciphertext” or “encrypted data”.
Two types of symmetric cryptographic algorithms are the so-called “block cipher” and the so-called “stream cipher”. Both types of algorithms use symmetric keys, i.e. the keys used for encryption and decryption are equal or trivially related. A block cipher is a cryptographic algorithm which splits an original set of data into a plurality of blocks of a given size, e.g. 64 bits per block. Mathematical and logical operations are performed on each block, whereby the original amount of data is usually transformed into blocks of pseudo-random data. In case decryption is initiated with the correct decryption key, the original data can be re-called by reversing the mathematical and logical operations used for encryption.
In a (synchronous) stream cipher, a pseudo-random number generator generates, based on a key, a sequence of pseudo-random numbers, the sequence being referred to as a keystream. The keystream is mixed, by arithmetic and/or logical operations, with a plurality of sub-sets of the original set of data, the sum of sub-sets of data defining the original data to be encrypted. The result of the mixing is the encrypted data. The set of encrypted data may be decrypted by repeating the procedure in such a way that the pseudo-random sequence is extracted from the encrypted data, so as to arrive at the original, decrypted data.
The plaintext is often mixed with the keystream by use of a logical operator, the so-called XOR operator, also referred to as the “exclusive or” operator, which is symbolized by the ⊕ symbol. XOR generates a one-bit result from two one-bit arguments. All possible combinations are:    0⊕0=0    0⊕1=1    1⊕0=1    1⊕1=0
Utilization of the XOR operator on a plaintext and a pseudo-random keystream yields a ciphertext. During decryption, an identical keystream is generated, and the XOR operator is now utilized on the keystream and the ciphertext, resulting in the original plaintext. The identical keystream can only be generated by using the key on which the keystream for encryption was initially based.
Further, so-called public key systems have been developed, such systems being characterized by a pair of asymmetric keys, i.e. a public key and a private key, the two keys being different. In such systems, the public key is usually used for encryption, and the private key is usually used for decryption. The private and the public key correspond to each other in a certain manner. The key which is used for encryption cannot be used for decryption, and vice versa. Thus, the public key may be published without violating safety in respect of accessibility of the original data. Accordingly, when transmitting encrypted data via a computer communications network, the recipient of the data first generates a set of keys, including a public and a private key. The public key, for example, is then provided to the sender of the data, whereas the private key is stored at a secure location. The sender of the data utilizes the public key for encrypting the original data, and the encrypted data are then transferred to the recipient. When the recipient receives the encrypted data, the private key, which corresponds to the public key previously utilized for encryption, is provided to the decryption system which processes the encrypted data so as to arrive at the original decrypted data. Public key systems are primarily used for transmitting keys which are utilized in, e.g., block or stream ciphers, which in turn perform encryption and decryption of the data.
The methods of the present invention are applicable to cryptographic methods, in particular but not exclusively to stream cipher algorithms, block cipher algorithms, Hash functions, and MAC (Message Authentication Code) functions. Such methods, functions and algorithms may include pseudo-random number generators which are capable of generating pseudo-random numbers in a reproducible way, i.e. in a way that results in the same numbers being generated in two different cycles when the same key is used as an input for the pseudo-random number generator in the two cycles.
In order to generate pseudo-random numbers, it has been proposed to utilize numerical solutions of chaotic systems, i.e. systems of non-linear differential equations or mappings exhibiting chaotic behavior. The term “chaotic” may in a strict mathematical sense only be used in the context of a continuous system. However, the present text also refers to discrete or finite systems having at least one positive Lyapunov exponent as being “chaotic”.
A chaotic system normally governs at least one state variable X, the numerical solution method of such a system normally comprising performing iteration or integration steps. In a chaotic system, the solution Xn at a given instant is dependent on the initial condition X0 to such an extent that a small deviation in X0 will result in a huge deviation in the solution Xn, the system often being referred to as exhibiting sensitivity on initial conditions. Thus, in order for the pseudo-random number generator, i.e. the algorithm numerically solving the chaotic system to give a reproducible stream of pseudo-random numbers, the exact initial condition X0 must be known. Thus, in cryptographic algorithms relying on chaotic systems, the initial condition X0 used in the numerical solution of the chaotic system is derived from the key entered by a user of the cryptographic system, thereby allowing the same stream of pseudo-random numbers to be generated for e.g. encryption and decryption of data.
Lyapunov exponents measure the rates of divergence or convergence of two neighboring trajectories, i.e. solution curves, and can be used to determine the stability of various types of solutions, i.e. determine whether the solution is for example periodic or chaotic. A Lyapunov exponent provides such a measure from a comparison between a reference orbit and a displaced orbit. Iterates of the initial condition X0 are denoted the reference orbit, and the displaced orbit is given by iterates of the initial condition X0+y0, where y0 is a vector of infinitely small length denoting the initial displacement. The initial orientation of the initial displacement is given by u0=y0/|y0|. Using this notation, the Lyapunov exponent, h(x0, y0), is defined as
      h    ⁡          (                        x          0                ,                  u          0                    )        =            lim              n        →        ∞              ⁢                  1        n            ⁢              ln        ⁡                  (                      |                          y              n                        |                          /                        |                          y              0                        |                    )                    where yn is the deviation of the displaced orbit from the reference orbit, given by the n'th iterate of x0. For systems whose dimension is larger than one, there is a set or spectrum of Lyapunov exponents, each one characterizing orbital divergence or convergence in a particular direction. Thus, if the system has N degrees of freedom, it will have N Lyapunov exponents which, however, are not necessarily distinct. In all practical situations, a positive Lyapunov exponent indicates chaos. The type of irregular behavior referred to as hyperchaos is characterized by two or more positive Lyapunov exponents. Numerical calculation of Lyapunov exponents may be performed according to the suggested method in T. S. Parker and L. O. Chua: Practical Numerical Algorithms for Chaotic Systems, pp. 73–81.
Even more irregular systems than hyperchaotic systems exhibit so-called turbulence, which refers to the type of behaviour exhibited by a system having a continuous spectrum of positive Lyapunov exponents. Turbulence may be modeled by partial differential equations, for example the well-known Navier-Stokes equations.
A large number of prior art documents are concerned with solving chaotic systems, in particular to be used in cryptographic algorithms, also including stream cipher algorithms relying on chaotic systems, some of which are briefly mentioned below as a general introduction to the background art.
U.S. Pat. No. 5,007,087 assigned to Loral Aerospace Corp. discloses a method and an apparatus for generating random numbers using chaos. The patent describes solving chaotic systems for generating random number sequences and mentions its possible use in cryptography, in particular in the field of key generation and management. The document mentions that repeatability of the number sequence should be avoided.
U.S. Pat. No. 5,048,086 assigned to Hughes Aircraft Company is related to an encryption system based on chaos theory. The system uses the logistic equation xn+1=μxn(1−xn), which is a mapping exhibiting chaos for certain values of μ. In the computations, floating-point operations are used.
U.S. Pat. No. 6,014,445 assigned to Kabushiki Kaisha Toshiba, Kawasaki, discloses an enciphering/deciphering apparatus and a method incorporating random variable and key-stream generation. The disclosure is related to chaotic stream ciphers and mentions that floating-point computations are used.
PCT Application WO 98/36523 assigned to Apple Computer, Inc. discloses a method of using a chaotic system to generate a public key and an adjustable back door from a private key. The need for establishing rules of precision during computations on a chaotic system is mentioned. The document states, as an example, that a specified floating point or fixed point precision can be identified along with specific standards for round-off.
“Numerical Methods and Software” by D. Kahaner, C. Moler and S. Nash (Prentice-Hall International Editions, 1989) contains a general introduction to (pseudo-)random number generation. The book mentions the following criteria for judging the quality of (pseudo-) random number generators:    a) High quality: the generator should pass all the statistical tests and have an extremely long period,    b) Efficiency: execution should be rapid and storage requirements minimal.    c) Repeatability: Specifying the same starting conditions will generate the same sequence.The user should be able to restart the generator at any time, but explicit initialization is not necessary. A slight change in the starting procedure will result in a different random sequence.    d) Machine independence and portability: The algorithm should work on different kinds of computers; in particular, no operation should cause the program to stop. The same sequence of random numbers should be produced on different computers by initializing the generator in exactly the same way.    e) Simplicity: The algorithm should be easy to implement and use.The book further states that no generator can be successful in satisfying all of these criteria.
“Secure Communication System Using Chaos via DSP Implementation” by H. Kamata, E. Tetsuro and Y. Ishida (IEEE 1996) describes a communication system based on a chaotic circuit, where a digital signal processor (DSP) is used in the implementation of the system.
By using fixed-point DSP, the system is made more robust than analog circuits. The recovery of a transmitted message is based on synchronizing the chaotic receiver system with the transmitter system.
It is known to use fixed-point variables in numerical computations, for example in Intel Mandelbrot computations. Intel (cf. MMX™ Technology Application Notes, “Implementing Fractals with MMX™ Technology”, publicly accessible on http:H/developer.intel.com/software/idap/resources/technical_collateral/mmx/MANDEL.HT M on Dec. 7, 2001) has explained how a Mandelbrot set (the set being derivable from a non-linear system) may be computed in a fast manner using MMX technology (an add-on to Intel's processors which speeds up certain computations). This is done using fixed-point computations.
The Mandelbrot set is computed by means of the below mapping:Zn+1=Zn2−μIntel utilizes a constant decimal separator position in their computations. A so-called 5.11 is utilized, i.e. a 16 bit number is utilized wherein the decimal separator is placed after the 5'th bit, “5” referring to 5 bits after the decimal separator, “11” referring to 11 bits after the decimal separator.